Non-Local Box

• [[quantum-computing]]
• $\begin{bmatrix} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 \end{bmatrix}$
• the above matrix is an NLB s.t. $a \oplus b$ = $x \wedge y$
• if Alice holds A and X and Bob holds B and Y, then for each user the probability of each output is $\frac{1}{2}$
  • from both players' PoV, their output (A and B respectively) is purely random, regardless of X and Y
• we assume that no communication was involved, i.e. Alice learns nothing about Y or B and Bob learns nothing about X or A
• [[cryptography]]
  • NLBs can be used to solve the [[socialist-millionaires-problem]]
  • $f : \left\{0,1\right\}^n \times \left\{0,1\right\}^n \to \left\{0,1\right\}$
  • we have the polynomials on bits
    • $\mathsf{And} = x \cdot y$
    • $\mathsf{Or} = x + y + x \cdot y$
    • $\mathsf{Not} = 1 + x$
  • any function on bits can be decomposed into a sum of monomials $f\left(x,y\right) = \sum_{i=1}^{2^n} P_i\left(x\right) \cdot Q_i\left(y\right)$
    • $2^n$ because each possible combination of $x$ has only one monomial in $y$
    • this is the [[fourier-tranform]] somehow? it's related to [[fourier-spectra]]?
  • notably, Alice can compute all $P_i$ to get a bitstring $\alpha$ and Bob can compute all $Q_i$ to get a bitstring $\beta$
    • these bitstrings are exponentially long ($2^n$ bits instead of $n$ bits)
  • this makes $f = \sum\alpha_i \cdot \beta_i = \vec{\alpha} \cdot \vec{\beta}$
  • now we apply the NLB: we want to turn the dot product of our single bit into a parity
  • if we have $\left(a_1,b_1\right) = \operatorname{NLB}_{\mathsf{And}}\left(\alpha_1,\beta_1\right)$ and $\left(a_2,b_2\right) = \operatorname{NLB}_{\mathsf{And}}\left(\alpha_2,\beta_2\right)$, then the dot product $\alpha \cdot \beta$ can be rewritten
    • $\alpha_1 \beta_1 + \alpha_2 \beta_2$
    • $a_1 \oplus b_1 + a_2 \oplus b_2$
    • $a_1 + b_1 + a_2 + b+2$
    • $\left(a_1 \oplus a_2\right) + \left(b_1 \oplus b_2\right)$
  • we can do the NLB exponentially-many times to get $\vec{a}$ and $\vec{b}$
    • this prevents either party from learning anything about the original $\vec{\alpha}$ or $\vec{\beta}$
  • we then do local computation following the rewrite rule for dot products
    • $r = \bigoplus \vec{a}$
    • $s = \bigoplus \vec{b}$
  • and we just need Bob to send $s$ to Alice, and she computes $r \oplus s$, and now she knows $f\left(x,y\right)$ without learning $y$
• three party case (real implementation)
  • promise that $x + y + z \equiv 0 \mod 2$
  • for an input $000$, the output is $000$ or $011$ or $101$ or $110$
  • for the other three inputs, the output is $001$ or $010$ or $100$ or $111$
  • for each party,
    • if they start with a 0, apply [[hadamard-gate]] and measure
    • if they start with a 1, phase by $i$ and measure
  • the parity of the output result reveals the And